import java.util.*;

/**
 * @ClassName MyMap
 * @Description TODO 存放地图的路线
 * @Author admin
 * @Date 2020/6/30 15:54
 * @Version 1.0
 **/
public class MyMap {

    // 所有城市的路线
    private Map<String, List<Way>> map = new HashMap();
    // 存储到达目的地所经过的城市
    private List<String> reachedWay = new ArrayList();
    // 储存到达目的地所经过的城市和所用的距离
    Map<String, Double> routeMap = new HashMap();

    /**
     * ----添加路线，双向添加---
     * @param city1
     * @param city2
     * @param distinct
     */
    public void addRoute(String city1, String city2, Double distinct) {
        // city1路线集合
        List<Way> cityList1 = map.get(city1);
        if (cityList1 == null) {
            cityList1 = new ArrayList();
            map.put(city1, cityList1);
        }

        // 生成路线1
        Way way1 = new Way(city1, city2, distinct);

        // 不存在该路线则添加路线
        if (!cityList1.contains(way1)) {
            cityList1.add(way1);
        }

        // city2路线集合
        List<Way> cityList2 = map.get(city2);
        if (cityList2 == null) {
            cityList2 = new ArrayList<>();
            map.put(city2, cityList2);
        }

        // 生成路线2
        Way way2 = new Way(city2, city1, distinct);
        if (!cityList2.contains(way2)) {
            cityList2.add(way2);
        }
    }

    /**
     * 获取最短路径
     * @param from
     * @param to
     */
    public void getTheShortestPath(String from, String to) {

        // 储存所花距离的临时变量
        Double tempDistinct = 0d;
        // 到达过的地区不重复走
        if (reachedWay.contains(from)) {
            return;
        }
        // 将经过的城市加入到reachedWay中
        reachedWay.add(from);
        if (reachedWay.size() > 1) {
            /*----------计算所花费的距离---------*/
            String firstCity = reachedWay.get(0);
            List<Way> initList = map.get(firstCity);
            for (Way way : initList) {
                // 如果目的地就是第二个城市就直接计算添加
                if (way.getTo().equalsIgnoreCase(reachedWay.get(1))) {
                    tempDistinct += way.getDistinct();
                }
            }



            for (int i = 1; i < reachedWay.size(); i++) {
                // 所经过的城市用时加起来
                List<Way> ways = map.get(reachedWay.get(i));
                for (int j = 0; j < ways.size(); j++) {
                    Way way = ways.get(j);
                    if (i + 1 < reachedWay.size()) {
                        if (way.getTo().equalsIgnoreCase(reachedWay.get(i + 1))) {
                            tempDistinct += way.getDistinct();
                        }
                    }
                }
            }
        }

        /*************************到达*******************/
        if (from.equalsIgnoreCase(to)) {
            // 最短路径赋值
            StringBuffer route = new StringBuffer();
            // 添加到路径当中
            reachedWay.forEach(item -> {
                if (route.length() == 0) {
                    route.append(item);
                } else {
                    route.append("->" + item);
                }
            });

            System.out.println(route + "\t 距离：" + tempDistinct);
            // 保存缓存
            routeMap.put(route.toString(), tempDistinct);
            tempDistinct = 0d;
            // 到达后回退 走下一条路线
            reachedWay.remove(reachedWay.size() - 1);
            return;
        }

        /*************************未到达*******************/
        List<Way> ways = map.get(from);
        for (Iterator iterator = ways.iterator(); iterator.hasNext();) {
            Way way = (Way) iterator.next();
            getTheShortestPath(way.getTo(), to);
        }

        // 到达后回退，走下一条路线
        reachedWay.remove(reachedWay.size() - 1);
    }

    public void showTheShortestPath(String city1, String city2) {
        getTheShortestPath(city1, city2);
        // 将routeMap 所有的距离值value选取最大的
        Map.Entry<String, Double> resultMap = routeMap.entrySet().stream()
                .min(Comparator.comparingDouble(Map.Entry::getValue)).get();
        System.out.println("\n最短路径为：\n" + resultMap.getKey()
                + "\t用时：" + resultMap.getValue());

    }

}
